//跳跃游戏 II
/*给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i] 
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]
*/
class Solution {
public:
    int find_jump_index(vector<int>& nums, int& jump_max, int left, int right) {
        int index = left;
        for (int i = left; i <= right; i++) {
            if (jump_max < nums[i] + i) {
                index = i;
                jump_max = nums[i] + i;
            }
        }
        return index;
    }
    int jump(vector<int>& nums) {
        if (nums.size() == 1)
            return 0;
        int jump_max = 0;
        int count = 1;
        int left = 0;
        int right = nums[0];
        while (right < nums.size() - 1) {
            left = find_jump_index(nums, jump_max, left, right);
            right = jump_max;
            count++;
        }
        return count;
    }
};

//H 指数
/*给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000
*/
class Solution {
    int h = 0;

public:
    int bs(vector<int>& nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int size = citations.size();
        int left = 0;
        int right = size - 1;
        for (int i = 1; i <= size; i++) {
            int temp = bs(citations, left, right, i);
            if (size - temp - 1 >= i) {
                h = i;
                left = temp + 1;
            } else {
                break;
            }
        }
        return h;
    }
};


//有效的数独
/*请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'
*/
class Solution {
    bool row[9][10] = {0};
    bool col[9][10] = {0};
    bool dig[3][3][10] = {0};

public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.size(); j++) {
                if (board[i][j] >= '0' && board[i][j] <= '9') {
                    if (row[i][board[i][j] - '0'] ||
                        col[j][board[i][j] - '0'] ||
                        dig[i / 3][j / 3][board[i][j] - '0'])
                        return false;
                    row[i][board[i][j] - '0'] = true;
                    col[j][board[i][j] - '0'] = true;
                    dig[i / 3][j / 3][board[i][j] - '0'] = true;
                }
            }
        }
        return true;
    }
};